package com.lsa.letcode.the22.generateValidParenth;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public List<String> generateParenthesis(int n) {
    	Map<String,String> dp = new HashMap<String,String>();
    	return inner(dp, n);
    }

	private List<String> inner(Map<String,String> dp, int n) {
		if (n == 1) {
    		return Arrays.asList("()");
    	}
    	else {
    		List<String> result = new ArrayList<String>();
    		List<String> subProbl = inner(dp, n - 1);
    		for (String sub : subProbl) {
    			String[] sols = new String[] {String.format("()%s", sub), String.format("(%s)", sub), String.format("%s()", sub)};
    			for (String sol : sols) {
					if (!dp.containsKey(sol)) {
						result.add(sol);
						dp.put(sol, null);
					}
				}
    		}
    		Collections.sort(result);
    		return result;
    	}
	}
}